package com.wenhao.leetcode.medium;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 题目：https://leetcode-cn.com/problems/merge-intervals/
 * 合并区间
 *
 * @author Wenhao Tong
 * @Description
 * @create 2021-06-29 12:57
 */
public class LeetCode56 {
    public static void main(String[] args) {
        LeetCode56 leetCode56 = new LeetCode56();
        int[][] merge = leetCode56.merge2(new int[][]{
                {1, 4},
                {4, 5},
                {5,6}
        });
        System.out.println();
    }

    /**
     * 这样做似乎有一些冗余，要不原地合并吧
     * @param intervals
     * @return
     */
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        List<int[]> result = new ArrayList<>();
        result.add(intervals[0]);
        for (int i = 1;i < intervals.length;i++) {
            if (result.get(result.size() - 1)[1] < intervals[i][0]) {
                result.add(intervals[i]);
            } else {
                result.get(result.size() - 1)[1] = intervals[i][1] > result.get(result.size() - 1)[1] ? intervals[i][1] : result.get(result.size() - 1)[1];
            }
        }
        int[][] ints = result.toArray(new int[result.size()][2]);
        return ints;
    }

    /**
     * 这一版超过了95%。。。
     * 一个数组而已，差别这么大的么。。。
     * @param intervals
     * @return
     */
    public int[][] merge2(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        int index = 0;
        for (int i = 1;i < intervals.length;i++) {
            if (intervals[index][1] >= intervals[i][0]) {
                intervals[index][1] = intervals[index][1] > intervals[i][1] ? intervals[index][1] : intervals[i][1];
            } else {
                intervals[++index] = intervals[i];
            }
        }
        int[][] result = new int[index + 1][2];
        for (int i = 0;i <= index;i++) {
            result[i] = intervals[i];
        }
        return result;
    }
}
